package sort;

import util.Comparator;

/**
 * 时间复杂度 O(N * log N)
 * 空间复杂度 O(1),
 * 不稳定
 *
 * @author Liaorun
 */
public class HeapSort implements Sortable {

    public static void main(String[] args) {
        Comparator comparator = new Comparator(10, 10);

        comparator.start(new HeapSort());
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // O(n)
        // 将arr数组变成一个大顶堆
//        for (int i = 0; i < arr.length; i++) {
//            // O(logN)
//            heapInsert(arr, i);
//        }

        // 将arr数组变成一个大顶堆,更快的方法
        // 为啥比一个一个点击 heapInsert更快？
        // 从最底层进行下沉操作，一直到堆顶
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }


        // 记录堆的长度
        int heapSize = arr.length;
        // 将堆顶元素放到最后面
        QuickSort.swap(arr, 0, --heapSize);

        // O(n)
        while (heapSize > 0) {
            // O(logN)
            // 第一个元素进行下沉
            // 这里需要证明 log1 + log2 + .. log N = N * log N
            heapify(arr, 0, heapSize);
            // O(1)
            // 将堆顶元素放到最后面
            QuickSort.swap(arr, 0, --heapSize);
        }
    }


    /**
     * 添加元素之后，保持数组代表大顶堆的方法
     *
     * @param arr   代表一个完全二叉树的数组
     * @param index 添加了元素的位置
     */
    public static void heapInsert(int[] arr, int index) {
        // 跳出情况：1.父节点比当前结点的值大，2.当前结点为根节点
        while (arr[index] > arr[(index - 1) / 2]) {
            QuickSort.swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }


    public static void heapify(int[] arr, int index, int heapSize) {
        // 左孩子的下标
        int left = index * 2 + 1;

        // 跳出情况：1.没有子节点；2. 下层过程中没有比自己大的子节点
        while (left < heapSize) {
            // 下方还有孩子的时候

            // 两个孩子中，谁的值大，把下标给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;

            // 父和较大的孩子之间，谁的值大，把下标给largest.
            largest = arr[largest] > arr[index] ? largest : index;

            if (largest == index) {
                // 子节点不比父节点大，不需要处理了，跳出循环
                break;
            }
            // 子节点比父节点大，需要交换父节点和较大的子节点
            QuickSort.swap(arr, largest, index);

            // 交换后，修改添加的位置为左节点的位置
            index = largest;

            // 重新计算左节点的位置
            left = index * 2 + 1;
        }
    }

    @Override
    public void sort(int[] arr) {
        heapSort(arr);
    }

    @Override
    public void sort(int[] arr, int k) {

    }
}
